#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
const int N = 100005;
int t, n, m;
int rd[N], cd[N], S[N];
stack <int> s;
struct node {
	int v;
	int id;
	bool flag;
};
vector <node> g[N];
int getf (int x) {
	if (S[x] == x) {
		return x;
	}
	return S[x] = getf(S[x]);
}
void merge (int x, int y) {
	int u = getf(x);
	int v = getf(y);
	if (u != v) {
		S[u] = v;
	}
}
void dfs (int u) {
	for (unsigned i = 0; i < g[u].size(); i++) {
		int v = g[u][i].v;
		if (!g[u][i].flag) {
			g[u][i].flag = 1;
			for (unsigned j = 0; j < g[v].size(); j++) {
				if (g[v][j].v == u) {
					g[v][j].v = 1;
				}
			}
			dfs (v);
		}
	}
	s.push(u);
}
int main() {
	scanf ("%d", &t);
	if (t == 1) {
		scanf ("%d%d", &n, &m);
		int a, b;
		for (int i = 1; i <= n; i++) {
			S[i] = i;
		}
		int mini = 200005;
		for (int i = 1; i <= m; i++) {
			scanf ("%d%d", &a, &b);
			g[a].push_back((node){b, i, 0});
			g[b].push_back((node){a, i, 0});
			merge (a, b);
			cd[a]++;
			cd[b]++;
			rd[a]++;
			rd[b]++;
			mini = min (mini, min (a, b));
		}
		int flag = 0, st = 0, ed = 0;
		for (int i = 1; i <= n; i++) {
			if (((cd[i] || rd[i]) && S[i] == i) || abs(cd[i] - rd[i]) > 1) {
				flag++;
			}
			if (cd[i] > rd[i]) {
				st++;
			} else if (cd[i] < rd[i]) {
				ed++;
			}
		}
		if (st > 1 || ed > 1 || flag > 1) {
			printf ("NO\n");
		} else {
			printf ("YES\n");
		}
		st = mini;
		for (int i = 1; i <= n; i++) {
			if ((cd[i] + rd[i]) % 2 == 1) {
				st = i;
				break;
			}
		}
		dfs(st);
		while (!s.empty()) {
			printf ("%d ", s.top());
			s.pop();
		}
	} else {
		scanf ("%d%d", &n, &m);
		int a, b;
		for (int i = 1; i <= n; i++) {
			S[i] = i;
		}
		int mini = 200005;
		for (int i = 1; i <= m; i++) {
			scanf ("%d%d", &a, &b);
			g[a].push_back((node){b, i ,0});
			merge (a, b);
			cd[a]++;
			rd[b]++;
			mini = min (mini, min (a, b));
		}
		int flag = 0, st = 0, ed = 0;
		for (int i = 1; i <= n; i++) {
			if (((cd[i] || rd[i]) && S[i] == i) || abs(cd[i] - rd[i]) > 1) {
				flag++;
			}
			if (cd[i] > rd[i]) {
				st++;
			} else if (cd[i] < rd[i]) {
				ed++;
			}
		}
		if (st > 1 || ed > 1 || flag > 1) {
			printf ("NO\n");
		} else {
			printf ("YES\n");
		}
		st = mini;
		for (int i = 1; i <= n; i++) {
			if (cd[i] % 2 == 1) {
				st = i;
				break;
			}
		}
		dfs(st);
		while (!s.empty()) {
			printf ("%d ", s.top());
			s.pop();
		}
	}
	return 0;
}
